package com.sliu.offer.binaryTreeNode;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如：前序遍历序列｛ 1, 2, 4, 7, 3, 5, 6, 8｝和中序遍历序列｛4, 7, 2, 1, 5, 3, 8，6}，
 * 重建出下图所示的二叉树并输出它的头结点。
 *
 * @author: sliu
 * @date: 2020/1/23 11:48
 **/

public class ReBuild {
    /**
     * 解题思路
     * 因为是树的结构，一般都是用递归来实现。
     * 用数学归纳法的思想就是，假设最后一步，就是root的左右子树都已经重建好了，那么我只要考虑将root的左右子树安上去即可。
     * 根据前序遍历的性质，第一个元素必然就是root，那么下面的工作就是如何确定root的左右子树的范围。
     * 根据中序遍历的性质，root元素前面都是root的左子树，后面都是root的右子树。那么我们只要找到中序遍历中root的位置，
     * 就可以确定好左右子树的范围。
     * 正如上面所说，只需要将确定的左右子树安到root上即可。递归要注意出口，假设最后只有一个元素了，那么就要返回
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length < 1 || in.length < 1) {
            return null;
        }
        int rootVal = pre[0];
        //数组长度仅为1的时候就要处理
        if (pre.length == 1) {
            return new TreeNode(rootVal);
        }
        return null;


    }
}
